package acwing._1_1AlgorithmBasic;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._1_1AlgorithmBasic._3SearchGraph
 * @File : _4_1NumberTheory.java
 * @Author : WangRuoyu
 * @Date : 2023/4/3 17:26
 */

public class _4_1NumberTheory {

    /*******质数的判定：试除法*******/
    static boolean isPrime(int x) {
        if (x <= 1) {
            return false;
        }
        for (int i = 2; i <= x / i; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    /*******分解质因数：试除法*******/
    static void divide(int x) {
        for (int i = 2; i <= x / i; ++i) {
            while (x % i == 0) {
                System.out.print(i + " ");
                x /= i;
            }
        }
        if (x > 1) System.out.print(x);
        System.out.println();
    }

    /*******筛质数*******/
    // 朴素筛法 O(nlogn)
    static int get_primes1(int n, int[] primes) {
        int cnt = 0;
        boolean[] st = new boolean[n + 1];
        for (int i = 2; i <= n; ++i) {
            if (!st[i]) {
                primes[cnt++] = i;
            }
            for (int j = i + i; j <= n; j += i) {
                st[j] = true;
            }
        }
        return cnt;
    }

    // 埃式筛法 O(nloglogn)
    static int get_primes2(int n, int[] primes) {
        int cnt = 0;
        boolean[] st = new boolean[n + 1];
        for (int i = 2; i <= n; ++i) {
            if (!st[i]) {
                primes[cnt++] = i;
                for (int j = i + i; j <= n; j += i) {
                    st[j] = true;
                }
            }
        }
        return cnt;
    }

    // 线性筛法（欧拉筛法） O(n)
    static int get_primes3(int n, int[] primes) {
        int cnt = 0;
        boolean[] st = new boolean[n + 1];
        for (int i = 2; i <= n; ++i) {
            if (!st[i]) {
                primes[cnt++] = i;
            }
            for (int j = 0; primes[j] <= n / i; j++) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
        return cnt;
    }

    /*******试除法求约数*******/
    static ArrayList<Integer> getDivisors(int n) {
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 1; i <= n / i; ++i) {
            if (n % i == 0) {
                res.add(i);
                if (i != n / i) {
                    res.add(n / i);
                }
            }
        }
        res.sort((o1, o2) -> o1 - o2);
        return res;
    }

    /*******约数个数*******/
    static int divisorNum(int k) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 2; i <= k / i; ++i) {
            if (k % i == 0) {
                int s = 0;
                while (k % i == 0) {
                    s++;
                    k /= i;
                }
                list.add(s);
            }
        }
        if (k > 1) {
            list.add(1);
        }
        int res = 1;
        for (int i = 0; i < list.size(); ++i) {
            res *= (list.get(i) + 1);
        }
        return res;
    }

    /*******约数之和*******/
    static int divisorSum(int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 2; i <= k / i; ++i) {
            if (k % i == 0) {
                if (!map.containsKey(i)) {
                    map.put(i, 0);
                }
                while (k % i == 0) {
                    map.put(i, map.get(i) + 1);
                    k /= i;
                }
            }
        }
        if (k > 1) {
            if (!map.containsKey(k)) {
                map.put(k, 0);
            }
            map.put(k, map.get(k) + 1);
        }
        int res = 1;
        for (Integer key : map.keySet()) {
            int tmp = 0;
            for (int i = 0; i <= map.get(key); ++i) {
                tmp = tmp * key + 1;
            }
            res *= tmp;
        }
        return res;
    }

    /*******欧几里得算法（辗转相除法）*******/
    // 欧几里得算法（辗转相除法）
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    // 更相减损术（辗转相减法）
    static int gcd2(int a, int b) {
        if (a < b) return gcd(b, a);
        if (b == 0) return a;
        int c = a - b;
        return gcd(Math.max(b, c), Math.min(b, c));
    }

    /*******欧拉函数*******/
    static int phi(int n) {
        int res = n;
        for (int i = 2; i <= n / i; ++i) {
            if (n % i == 0) {
                res = (res / i) * (i - 1);
                while (n % i == 0){
                    n /= i;
                }
            }
        }
        if (n > 1) {
            res = res / n * (n - 1);
        }
        return res;
    }

    // 线性筛法求欧拉函数之和
    static long phiSum(int n) {
        int cnt = 0;
        int[] primes = new int[n + 1];
        int[] p = new int[n + 1];
        boolean[] st = new boolean[n + 1];

        p[1] = 1;
        for (int i = 2; i <= n; ++i) {
            if (!st[i]) {
                primes[cnt++] = i;
                p[i] = i - 1;
            }
            for (int j = 0; primes[j] <= n / i; ++j) {
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) {
                    p[primes[j] * i] = primes[j] * p[i];
                    break;
                }
                p[primes[j] * i] = (primes[j] - 1) * p[i];
            }
        }

        long res = 0;
        for (int i = 1; i < p.length; ++i) {
            res += p[i];
        }
        return res;
    }

    /*******快速幂*******/
    public long quickPower(long a, int k, int p) {
        long res = 1;
        while (k > 0) {
            if ((k & 1) == 1) res = (res * a) % p;
            k >>= 1;
            a = a * a % p;
        }
        return res;
    }

    /*******扩展欧几里得算法*******/
    static long exgcd(long a, long b, long[] x, long[] y) {
        if (b == 0) {
            x[0] = 1;
            y[0] = 0;
            return a;
        }
        long d = exgcd(b, a % b, y, x);
        y[0] -= a / b * x[0];
        return d;
    }
}

